package fireway;

/**
 * 快速排序算法(快速排序之后使用插入排序)
 * 2018年 08月 05日 星期日
 *
 * @author fireway
 */
public class QuickSort {
    private long mLArray[];

    private int mSize;

    private static final int INSERT_SORT_SIZE = 10;

    public QuickSort(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public void insert(long e) {
        mLArray[mSize++] = e;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    private void swap(int left, int right) {
        long temp = mLArray[left];
        mLArray[left] = mLArray[right];
        mLArray[right] = temp;
    }

    public void quickSort() {
        recQuickSort(0, mSize - 1);
        insertSort(0, mSize - 1);
    }

    private void recQuickSort(int left, int right) {
        int size = right - left + 1;
        if (size < INSERT_SORT_SIZE) {
            // do nothing
        } else {
            long median = medianOfThreeItem(left, right);
            int partitionIndex = partitioning(left, right, median);
            recQuickSort(left, partitionIndex - 1);
            recQuickSort(partitionIndex + 1, right);
        }
    }

    private void insertSort(int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            long temp = mLArray[i];
            int j = i;
            while (j > left && mLArray[j - 1] >= temp) {
                mLArray[j] = mLArray[j - 1];
                j--;
            }
            if (j != i) {
                mLArray[j] = temp;
            }
        }
    }

    private long medianOfThreeItem(int left, int right) {
        int middle = (left + right) / 2;
        // left center
        if (mLArray[left] > mLArray[middle]) {
            swap(left, middle);
        }
        // left right
        if (mLArray[left] > mLArray[right]) {
            swap(left, right);
        }
        // center right
        if (mLArray[middle] > mLArray[right]) {
            swap(middle, right);
        }

        swap(middle, right - 1);

        return mLArray[right - 1];
    }

    private int partitioning(int left, int right, long pivot) {
        int leftPointer = left;
        int rightPointer = right - 1;

        while(true) {
            while(mLArray[++leftPointer] < pivot) {}

            while(mLArray[--rightPointer] > pivot) {}

            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(leftPointer, rightPointer);
            }
        }
        swap(leftPointer, right - 1);

        return leftPointer;
    }
}
